560. Subarray Sum Equals K

Solution 1: Brute-Force (TLE)

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ans = 0
        n = len(nums)
        for i in range(n):
            subSum = 0
            for j in range(i, n):
                subSum += nums[j]
                if subSum == k:
                    ans += 1
        return ans

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution 2: PrefixSum + Hash

from collections import Counter
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ans = 0
        prefixSumHistory = Counter({
            0: 1 # Init
        })
        currPrefixSum = 0
        for i in range(len(nums)):
            currPrefixSum += nums[i]
            complementSum = currPrefixSum - k
            if complementSum in prefixSumHistory:
                ans += prefixSumHistory[complementSum]
            prefixSumHistory[currPrefixSum] += 1
        return ans

Time Complexity: O(n)
Space Complexity: O(n)

Reference

https://www.youtube.com/watch?v=mKXIH9GnhgU

Follow-ups

523. Continuous Subarray Sum